package leetcode;

public class T79 {
    public boolean exist(char[][] board, String word) {
        int[][] visited = new int[board.length][board[0].length];
        for (int x = 0; x < board[0].length; x++) {
            for (int y = 0; y < board.length; y++) {
                visited[y][x]  = 0;
            }
        }
        for (int x = 0; x < board[0].length; x++) {
            for (int y = 0; y < board.length; y++) {
                boolean f = f(board, word, x, y, 0,visited);
                if (f) {
                    return f;
                }
            }
        }
        return false;

    }

    private boolean f(char[][] board, String word, int x, int y, int index, int visited[][]) {
        if (index == word.length()) {
            return true;
        }

        if (x < 0 || x >= board[0].length) {
            return false;
        }
        if (y < 0 || y >= board.length) {
            return false;
        }

        if (board[y][x] != word.charAt(index)) {
            return false;
        }
        if (visited[y][x] == 1) {
            return false;
        }


        boolean result = false;
        visited[y][x] = 1;
        result |= f(board, word, x + 1, y, index + 1, visited);
        if(result) return result;

        result |= f(board, word, x - 1, y, index + 1, visited);
        if(result) return result;

        result |= f(board, word, x, y + 1, index + 1, visited);
        if(result) return result;

        result |= f(board, word, x, y - 1, index + 1, visited);
        if(result) return result;

        visited[y][x] = 0;

        return result;
    }

    public static void main(String[] args) {
        T79 t79 = new T79();
        char[][] borad = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "SEE";
        boolean exist = t79.exist(borad, word);
        System.out.println(exist);
    }

}
